package iddfs;

import java.util.Stack;

import graph.Node;

public class IDDFS {
	long maxMemory;

	public IDDFS(){
		maxMemory = 0;
	}

	public boolean solve(Node root){
		//		boolean isSolved = false;
		//		Node[] solution = null;
		boolean solution = false;;
		//		root.visit(0);
		//root marked in 1st iteration - iternum = 1
		root.mark(getMarkNum(0,-1));
		for (int depth = 1; !solution ; depth=incDepth(depth)){
			//			System.out.println("Starting iteration- #"+depth);
			root.mark(getMarkNum(depth, -1));
			solution = runDFS(depth, root);
			//			if (solution!=null){
			//				isSolved = true;
			//			}
		}
		return solution;
	}

	protected int incDepth(int depth) {
		return depth+1;
	}
	protected int getMarkNum(int iterNum, int fathersDepth) {
		return iterNum-(fathersDepth+1);
	}

	private static class IntNode{
		int depth;
		Node node;
		public IntNode(int depth, Node node){
			this.depth = depth;
			this.node = node;
		}
	}

	public boolean runDFS(int depth, Node root){
		Stack<IntNode> nodes = new Stack<IntNode>();
		nodes.push(new IntNode(0,root));
		IntNode goal = null;
		while(!nodes.empty() && goal==null){
			IntNode node = nodes.pop();
			if (node.node.isGoal()){
				goal = node;
			} else if (node.depth < depth){
				Node[] children = node.node.getChildren();
				int newDepth = node.depth+1;
				for (int i=0; i<children.length; i++){
					children[i].mark(children[i].getNumMarks());
					nodes.push(new IntNode(newDepth, children[i]));
					maxMemory = Math.max(maxMemory, nodes.size());
				}
			}
		}
		if (goal == null) return false;
		return true;
	}

	public long getMaxMemory() {
		return maxMemory;
	}

}
